package 回溯算法;

import java.util.*;

public class 组合总和Ⅱ {
    class Solution{
        List<List<Integer>> lists = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0;
        public List<List<Integer>> combinationSum(int[] candidates,int target ){
            //先将数组按顺序排列先
            Arrays.sort(candidates);
            boolean[] flag = new boolean[candidates.length];
            bcakTracking(candidates,target,0,flag);
            return lists;
        }

        public void bcakTracking(int[] arr, int target, int index, boolean[] flag) {
           //终止条件
            if (sum == target) {
                lists.add(new ArrayList<>(deque));
                return;
            }
            for (int i = index; i < arr.length && arr[i]+sum<=target; i++) {

                //出现重复节点，同层的第一个节点被访问过，所以直接跳过
                //这段码的意思我觉得是判断当前的这个元素是否和前一个元素相同，毕竟一开始已经排序好了
                //flag也是判断是否和前面的不一致，不一致意思前一个使用过 后一个没使用过 所以跳过第一个
                if (i>0 && arr[i]==arr[i-1] && !flag[i-1]){
                    continue;
                }
                flag[i] = true;
                sum+=arr[i];
                deque.push(arr[i]);
                bcakTracking(arr,target,index+1,flag);
                //回溯
                int temp = deque.pop();
                flag[i] = false;
                sum -= temp;

            }

        }
    }
}
